package nf.graph;

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
import java.util.NoSuchElementException;

class BreadthFirstTraverser implements Iterable<Path>
{
	private Graph graph;
	private Node start;
	
	/**
	 * Creates a new breadth-first traverser for the given graph.
	 * @param graph the graph to be traversed
	 * @param node the initial node
	 */
	public BreadthFirstTraverser(Graph graph, Node node)
	{
		this.graph = graph;
		this.start = node;
	}
	
	/**
	 * Returns a traversal node iterator
	 * @return Traversal node iterator
	 */
	public Iterator<Path> iterator()
	{
	    return new TraversionIterator();
	}
	
	/**
	 * Creates a map of all shortest paths reachable from the traverser's
	 * start node.
	 */
	public Map<Node, Path> createMap()
	{
		Map<Node, Path> map = new HashMap<Node, Path>();
		
		for (Path path : this) {
			map.put(path.getTail(), path);
		}
		
		return map;
	}
	
	private class TraversionIterator implements Iterator<Path>
	{
		private HashSet<Node> seen;
		private Queue<Path> pending;
		
		public TraversionIterator()
		{
			seen = new HashSet<Node>();
			pending = new LinkedList<Path>();
			
			pending.offer(new Path(start));
		}
		
		public boolean hasNext()
		{
			return pending.peek() != null;
		}
		
		public Path next() throws NoSuchElementException
		{
			Path curPath = pending.remove();
			Path neighborPath;
			List<Node> neighbors = graph.getNeighbors(curPath.getTail());
			
			if (neighbors == null) {
				throw new RuntimeException("Node " +
					curPath.getTail().toString() +
					" should be in the graph, but is not.");
			}
			
			for (Node neighbor : neighbors) {
				if (!seen.add(neighbor)) // returns false if neighbor is seen
					continue;
				
				pending.offer(curPath.extend(neighbor));
			}
			
			return curPath;
		}
		
		public void remove()
		{
			throw new UnsupportedOperationException();
		}
	}
}
